|
|
|
 |
|
|
|
|
 |
 |
 |
 |
 |
 |
 |
July 20, 2007 |
Alberta researchers solve checkers
By SHANNON MONTGOMERY
|
EDMONTON (CP) - It's taken dozens of computers humming away for almost 18 years, but a University of Alberta team has finally solved every possible game of checkers and concluded that as long as no mistakes are made, the game will end in a draw. The popular game may be simple to play, but it holds a potential 500 billion billion positions. That's one million times more complicated than any other game solved before, says Jonathan Schaeffer, the computer science professor who began the project in 1989. "In hindsight, it was ludicrous. Why tackle something a million times bigger?" said the wiry-haired academic. "Maybe there's a little bit of craziness there." To conceptualize that number, Schaeffer says to picture one million checkers positions fitting into a footprint. To reach the number of possible positions would take a step on every part of the surface of the world. "You appreciate how long it would take you to do that - it's a big task. Well, we had to do that with computers, essentially. So it's huge." But they did trim down the number of positions examined. For example, if a move in a certain position would lead to a win, the computer wouldn't look at other possible moves from that position that may lead to a draw or loss. Schaeffer's proof was to be published in the academic journal Science on Thursday. "I was floored by the news when I heard it. I thought it was, from a game-playing point of view, quite an exciting development," said computer science professor Michael Genesereth of Stanford University in California. "Games like chess and checkers have long been thought to be so complex that being able to determine for sure whether it is a win, loss or draw - people have thought for a long time that it would be impossible to make that determination." While Schaeffer's first gaming love is chess, he said it became clear to him in the late 1980s that IBM's Deep Blue was ahead of the competition in terms of computer chess. "My friends said, 'If you want to win, why not checkers?' " Just a year later, his program, Chinook, earned the right to play for the human world checkers championship. Chinook played that match in 1992 and narrowly lost to Marion Tinsley, who had lost only a handful of games in his four-decade career. The two reunited two years later for a rematch, but Chinook won by default when Tinsley had to withdraw due to illness. The computer then captured the next two world championships, at which time it retired, Schaeffer said. The matchup between man and machine had become so uneven as to be unfair. Work on the project ground to a halt not long afterward. Computers at the time were only capable of conceptualizing numbers up to four billion, but to continue his work Schaeffer needed more. He at first tried to program around the problem, but then decided to sit back and let technology catch up. By 2001, the end was in sight. In April of this year, "the program stopped and said, 'Game over. It's a draw,' " Now, Chinook is capable of taking every game to a win or a draw. "There are some very good humans out there that can play the computer to a draw in most games. But humans are fallible, humans make mistakes," said Schaeffer. "And my program will never lose." In Canada, checkers has always been the domain of Quebec. The Quebec checkers association runs the link to the world checkers community and the Canadian championship starts Thursday in Montreal. Internationally, checkers is usually played on a board with 10 squares to a side. But many Canadians will be more familiar with the size of board Chinook uses, which is eight squares by eight squares. "We try to promote mostly the international game, because we feel it's the one that is played by the most people, and we'll argue also that it's the one giving the most interesting possibilities," said Andre Leclerc, general manager of the group that runs the Quebec association. Leclerc said computers will never play like humans. "Some players are more careful and, I guess, they're maybe afraid to lose," he said. "Some players are known to be like gladiators. They play with no fear and they play for the win. They try to trick their opponent." Both Schaeffer and Genesereth say that while the discovery is exciting from a computer science perspective, it shouldn't change how humans play the game. "I think checkers, chess and other games will continue to be interesting, even if it turns out that computers can, in principle, beat them," said Genesereth. Although his checkers obsession is coming to a close, Schaeffer said his lab isn't done with artificial gaming. It has developed poker-playing software that is about to be tested next week against two of the top professional human players at an artificial intelligence conference in Vancouver. On the Web: |
